package computation;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import primatives.PointND;
import util.ClusterEdge;
import util.VertexDistance;

public class Graphs
{
	// sort-order = short distance first, longest last
    private static final Comparator<VertexDistance> VERTEX_ORDER = new Comparator<VertexDistance>()
    {
        public int compare(VertexDistance v1, VertexDistance v2)
        {
    		if (v1.distance < v2.distance) return -1;
    		else if (v1.distance == v2.distance) return 0;
    		else return 1;
        }
    };
	
	/**
	 * Returns the MST of a set of vertices using the Euclidean distance as a measure of length.
	 * Uses Kruskal's algorithm for finding the MST.
	 * @param vertices - set of vertices.
	 * @param eps - parameter which determines which edges to drop.
	 * @return List of edges which make up the MST.
	 */
	public static ArrayList<ClusterEdge> MST_Euclidean(ArrayList<PointND> vertices, int limit_fraction)
	{
		ArrayList<ClusterEdge> mst = new ArrayList<ClusterEdge>();
		
		ArrayList<ArrayList<PointND>> forest = new ArrayList<ArrayList<PointND>>();
		
		ArrayList<ClusterEdge> complete = new ArrayList<ClusterEdge>(); // first create the complete graph over all vertices
		
		int edge_limit = vertices.size()/limit_fraction; // number of edges created per vertex in the "complete" graph
		
		System.out.print("Creating complete graph over "+vertices.size()+" vertices... ");
		for (PointND v : vertices)
		{
			LinkedList<VertexDistance> distances = new LinkedList<VertexDistance>();
			for (PointND u : vertices)
			{
				double dist = v.get_distance(u, 3); // only care about x,y,z
				distances.addLast(new VertexDistance(dist, u));
			}
			
			Collections.sort(distances, VERTEX_ORDER);
			
			// only considered the edge_limit number of closest edges
			for (int i = 0; i < edge_limit; i++)
			{
				VertexDistance vd = distances.remove();
				complete.add(new ClusterEdge(v, vd.pt));
			}
			
			// create a new forest of trees
			ArrayList<PointND> set = new ArrayList<PointND>();
			set.add(v);
			forest.add(set);
		}
		System.out.println(" done! ["+complete.size()+"]");
		
		System.out.print("Sorting edges... ");
		Collections.sort(complete); // sort the edges
		System.out.println(" done!");
		
		System.out.print("Finding MST (Krushals)... ");
		// compute the MST using Krushals algorithm
		while (complete.size() > 0)
		{
			ClusterEdge e = complete.remove(0);
			PointND a = e.start;
			PointND b = e.end;
			
			// if that edge connects two different trees, then add it to the forest, combining two trees into a single tree
			int i = 0, j = 0;
			boolean stop_i = false, stop_j = false; // this is pretty ugly but sorta needed
			for (ArrayList<PointND> tree: forest)
			{
				if (tree.contains(a)) stop_i = true;
				if (tree.contains(b)) stop_j = true;
				
				if (!stop_i) i++;
				if (!stop_j) j++;
				
				if (stop_i && stop_j) break; // early exit?
			}
			
			if (!(i == j))
			{
				ArrayList<PointND> t1 = null, t2 = null;
				if (i < j) { // gotta check since if we remove i first then if j is bigger we'll need j-1.. or we can just switch the removals
					t1 = forest.remove(j);
					t2 = forest.remove(i);
				} else {
					t1 = forest.remove(i);
					t2 = forest.remove(j);
				}
				
				t1.addAll(t2); //combine them!
				forest.add(t1);
				mst.add(e);
			}
		}
		System.out.println(" done!");
		
		
		// sum up the total weight
		
		return mst;
	}

}
